package com.chengzhi.structure;


import java.util.*;
import java.util.LinkedList;

/**
 * @description: avl树
 * @author: ruanchengzhi
 * @create: 2020/3/5 16:36
 **/
public class AVL<E extends Comparable<E>> {
    private Node<E> root;
    private int size;

    public AVL() {
        this.root = null;
        this.size = 0;
    }

    public Node<E> getRoot() {
        return root;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 插入数据
     *
     * @param e
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node<E> node, E e) {
        if (null == node) {
            size++;
            return new Node(e);
        }
        if (node.value.compareTo(e) > 0) {
            node.left = add(node.left, e);
        } else if (node.value.compareTo(e) < 0) {
            node.right = add(node.right, e);
        } else {
            node.value = e;
        }
        //计算树的高度
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        int balance = getBalanceFactor(node);
        //LL 右旋
        if (balance > 1 && getBalanceFactor(node.left) >= 0) {
            return rightRotate(node);
        }
        //RR  左旋
        if (balance < -1 && getBalanceFactor(node.right) <= 0) {
            return leftRotate(node);
        }
        //LR 左旋在右旋
        if (balance > 1 && getBalanceFactor(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        //RL 右旋在左旋
        if (balance < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

    // 对节点y进行向右旋转操作，返回旋转后新的根节点x
    //        y                              x
    //       / \                           /   \
    //      x   T4     向右旋转 (y)        z     y
    //     / \       - - - - - - - ->    / \   / \
    //    z   T3                       T1  T2 T3 T4
    //   / \
    // T1   T2
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T3 = x.right;

        // 向右旋转过程
        x.right = y;
        y.left = T3;

        // 更新height
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        return x;
    }


    // 对节点y进行向左旋转操作，返回旋转后新的根节点x
    //    y                             x
    //  /  \                          /   \
    // T1   x      向左旋转 (y)       y     z
    //     / \   - - - - - - - ->   / \   / \
    //   T2  z                     T1 T2 T3 T4
    //      / \
    //     T3 T4
    private Node leftRotate(Node y) {
        Node x = y.right;
        Node T2 = x.left;

        // 向左旋转过程
        x.left = y;
        y.right = T2;

        // 更新height
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
        return x;
    }

    /**
     * 判断是否存在
     *
     * @param e
     * @return: boolean
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public boolean contains(E e) {
        if (Objects.isNull(root)) {
            return false;
        }
        return contains(root, e);
    }

    private boolean contains(Node<E> root, E e) {
        if (root.value.equals(e)) {
            return true;
        } else if (root.value.compareTo(e) < 0) {
            return contains(root.left, e);
        } else if (root.value.compareTo(e) > 0) {
            return contains(root.right, e);
        }
        return false;
    }

    /**
     * 深度优先-前序遍历(先打印参数 中序遍历（中间打印） 后序遍历（最后打印）)
     *
     * @param
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node<E> root) {
        if (Objects.isNull(root)) {
            return;
        }
        System.out.println(root.value);
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 广度优先遍历层次遍历（利用队列queue）
     *
     * @param
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public void breadthOrder() {
        Queue<Node<E>> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node Node = queue.remove();
            System.out.println(Node.value);
            if (Objects.nonNull(root.left)) {
                queue.add(root.left);
            }
            if (Objects.nonNull(root.right)) {
                queue.add(root.right);
            }
        }
    }

    /**
     * 删除最小节点
     *
     * @param
     * @return: E
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public E deleteMinNode() {
        if (size == 0) {
            throw new IllegalArgumentException("bst is empty");
        }
        Node<E> minNode = getMinNode(root);
        root = deleteMinNode(root);
        return minNode.value;
    }

    private Node<E> deleteMinNode(Node<E> root) {
        if (root.left == null) {
            Node<E> rightNode = root.right;
            root.right = null;
            size--;
            return rightNode;
        }
        root.left = deleteMinNode(root.left);
        return root;
    }


    private Node<E> getMinNode(Node<E> Node) {
        if (Node.left == null) {
            return Node;
        }
        return getMinNode(Node.left);
    }

    /**
     * 删除最大节点
     *
     * @param
     * @return: E
     * @author: ruanchengzhi
     * @date: 2020/3/5
     */
    public E deleteMaxNode() {
        if (size == 0) {
            throw new IllegalArgumentException("bst is empty");
        }
        Node<E> maxNode = getMaxNode(root);
        root = deleteMaxNode(root);
        return maxNode.value;
    }

    private Node<E> deleteMaxNode(Node<E> root) {
        if (root.right == null) {
            Node<E> leftNode = root.left;
            root.left = null;
            size--;
            return leftNode;
        }
        root.right = deleteMaxNode(root.right);
        return root;
    }

    private Node<E> getMaxNode(Node<E> Node) {
        if (Node.right == null) {
            return Node;
        }
        return getMaxNode(Node.right);
    }

    /**
     * 删除节点
     *
     * @param e
     * @return: void
     * @author: ruanchengzhi
     * @date: 2020/3/6
     */
    public void deleteNode(E e) {
        root = deleteNode(root, e);
    }

    private Node<E> deleteNode(Node<E> node, E e) {
        if (node == null) {
            return null;
        }
        Node ret;
        if (node.value.compareTo(e) < 0) {
            node.right = deleteNode(node.right, e);
            ret = node;
        } else if (node.value.compareTo(e) > 0) {
            node.left = deleteNode(node.left, e);
            ret = node;
        } else {
            //左子树为空
            if (Objects.isNull(node.left)) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                ret = rightNode;
            } else if (Objects.isNull(node.right)) {
                //右子树为空
                Node leftNode = node.left;
                node.left = null;
                size--;
                ret = leftNode;
            } else {
                //左右子树都不为空 找到当前右子树最小值替换当前值 并删除
                Node<E> minNode = getMinNode(node.right);
                minNode.right = deleteNode(node.right, minNode.value);
                minNode.left = node.left;
                node.left = node.right = null;
                ret = minNode;
            }
        }
        if (null == ret) {
            return null;
        }
        //计算树的高度
        ret.height = Math.max(getHeight(ret.left), getHeight(ret.right)) + 1;
        int balance = getBalanceFactor(ret);
        //LL 右旋
        if (balance > 1 && getBalanceFactor(ret.left) >= 0) {
            return rightRotate(ret);
        }
        //RR  左旋
        if (balance < -1 && getBalanceFactor(ret.right) <= 0) {
            return leftRotate(ret);
        }
        //LR 左旋在右旋
        if (balance > 1 && getBalanceFactor(ret.left) < 0) {
            ret.left = leftRotate(ret.left);
            return rightRotate(ret);
        }
        //RL 右旋在左旋
        if (balance < -1 && getBalanceFactor(ret.right) > 0) {
            ret.right = rightRotate(ret.right);
            return leftRotate(ret);
        }
        return ret;
    }

    /**
     * 节点的高度
     *
     * @param node
     * @return: int
     * @author: ruanchengzhi
     * @date: 2020/3/17
     */
    private int getHeight(Node node) {
        if (null == node) {
            return 0;
        }
        return node.height;
    }

    /**
     * 平衡因子
     *
     * @param root
     * @return: int
     * @author: ruanchengzhi
     * @date: 2020/3/17
     */
    private int getBalanceFactor(Node<E> root) {
        if (null == root) {
            return 0;
        }
        return getHeight(root.left) - getHeight(root.right);
    }

    public boolean isBST() {
        List<E> list = new ArrayList<>();
        isBST(root, list);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i - 1).compareTo(list.get(i)) > 0) {
                return false;
            }
        }
        return true;
    }

    private void isBST(Node<E> root, List<E> list) {
        if (null == root) {
            return;
        }
        isBST(root.left, list);
        list.add(root.value);
        isBST(root.right, list);
    }

    public boolean isBalance() {
        return isBalanced(root);
    }

    // 判断以Node为根的二叉树是否是一棵平衡二叉树，递归算法
    private boolean isBalanced(Node node) {

        if (node == null) {
            return true;
        }
        int balanceFactor = getBalanceFactor(node);
        if (Math.abs(balanceFactor) > 1) {
            return false;
        }
        return isBalanced(node.left) && isBalanced(node.right);
    }


    class Node<E> {
        int height;
        E value;
        Node<E> left;
        Node<E> right;

        public Node(E value) {
            this.value = value;
            this.left = null;
            this.right = null;
            height = 1;
        }

    }
}
